package com.fr.lintcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
*作者：furong
*日期：2017年3月10日
*时间：下午5:59:25
*/
public class Q370 {
    /**
     * @param expression: A string array
     * @return: The Reverse Polish notation of this expression
     */
    public ArrayList<String> convertToRPN(String[] expression) {
        ExpressionTreeNode node = build(expression);
        ArrayList<String> rs = new ArrayList<>();
        if (node == null) {
            return rs;
        }
        String s = node.toString();
        String[] ss = s.split(",");
        for (String item : ss) {
            if (item.length() > 0) {
                rs.add(item);
            }
        }
        return rs;
    }

    public class ExpressionTreeNode {
        public String symbol;
        public ExpressionTreeNode left, right;

        public ExpressionTreeNode(String symbol) {
            this.symbol = symbol;
            this.left = this.right = null;
        }

        @Override
        public String toString() {
            return (left == null ? "" : left.toString()) + "," + (right == null ? "" : right.toString()) + "," + symbol;
        }

    }

    /**
     * @param expression: A string array
     * @return: The root of expression tree
     */
    static int count = 0;
    Map<String, ExpressionTreeNode> map = new HashMap<>();

    public ExpressionTreeNode build(String[] expression) {
        Stack<String> stack = new Stack<>();
        // 去括号
        for (String s : expression) {
            if (")".equals(s)) {
                List<String> list = new ArrayList<>();
                while (!stack.isEmpty()) {
                    String v = stack.pop();
                    if ("(".equals(v)) {
                        stack.push(headle(list));
                        break;
                    } else {
                        list.add(0, v);
                    }
                }
            } else {
                stack.add(s);
            }
        }
        List<String> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            list.add(0, stack.pop());
        }
        return map.get(headle(list));
    }

    private String headle(List<String> list) {
        if (list.size() <= 0) {
            return "#-1";
        }
        boolean hasSymbol = true;
        while (hasSymbol) {
            hasSymbol = false;
            for (int i = 0; i < list.size(); i++) {
                String s = list.get(i);
                if ("*".equals(s) || "/".equals(s)) {
                    hasSymbol = true;
                    ExpressionTreeNode node = createExpressionTreeNode(s);
                    node.left = createExpressionTreeNode(list.get(i - 1));
                    node.right = createExpressionTreeNode(list.get(i + 1));
                    list.remove(i - 1);
                    list.remove(i - 1);
                    list.remove(i - 1);
                    list.add(i - 1, "#" + count);
                    map.put("#" + count, node);
                    count++;
                    break;
                }
            }
        }
        hasSymbol = true;
        while (hasSymbol) {
            hasSymbol = false;
            for (int i = 0; i < list.size(); i++) {
                String s = list.get(i);
                if ("+".equals(s) || "-".equals(s)) {
                    hasSymbol = true;
                    ExpressionTreeNode node = createExpressionTreeNode(s);
                    node.left = createExpressionTreeNode(list.get(i - 1));
                    node.right = createExpressionTreeNode(list.get(i + 1));
                    list.remove(i - 1);
                    list.remove(i - 1);
                    list.remove(i - 1);
                    list.add(i - 1, "#" + count);
                    map.put("#" + count, node);
                    count++;
                    break;
                }
            }
        }
        String tmp = list.get(0);
        if (tmp.startsWith("#")) {
        } else {
            ExpressionTreeNode node = createExpressionTreeNode(tmp);
            tmp = "#" + count;
            map.put(tmp, node);
            count++;
        }
        return tmp;
    }

    private ExpressionTreeNode createExpressionTreeNode(String s) {
        if (s.startsWith("#")) {
            return map.get(s);
        } else {
            ExpressionTreeNode node = new ExpressionTreeNode(s);
            return node;
        }
    }
}
